package com.lun.swordtowardoffer2.c10;

public class MagicDictionary {

	static class TrieNode{
		public static final int ENGLISH_LOWER_LETTER_TOTAL_NUM = 'z' - 'a' + 1;
		public TrieNode[] children;
		public boolean isWord;
		public TrieNode() {
			children = new TrieNode[ENGLISH_LOWER_LETTER_TOTAL_NUM];
		}
	}
	
	TrieNode root;
	
	public MagicDictionary() {
		root = new TrieNode();
	}
	
	public void buildDict(String[] dict) {

		for(String str : dict) {
			TrieNode node = root;
			for(char ch : str.toCharArray()) {
				int index = ch - 'a';
				if(node.children[index] == null) {
					node.children[index] = new TrieNode();
				}
				node = node.children[index];
			}
			
			node.isWord = true;
		}
	}
	
	public boolean search(String word) {
		return dfs(root, word, 0, 0);
	}

	private boolean dfs(TrieNode node, String word, int index, int editNum) {
		if(node == null)
			return false;
		
		if(node.isWord && index == word.length() && editNum == 1) {
			return true;
		}
		
		if(index < word.length() && editNum <= 1) {
			boolean found = false;
			for(int j = 0; j < TrieNode.ENGLISH_LOWER_LETTER_TOTAL_NUM && !found; j++) {
				int nextEditNum = (j == word.charAt(index) - 'a' ? editNum : editNum + 1);
				found = dfs(node.children[j], word, index + 1, nextEditNum);
			}
			return found;
		}
		return false;
	}
	
}
